package exam.wangyi8_21;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.List;
import java.util.Queue;

public class test4 {


    public static int minSailCost (int[][] input) {
        // write code here
        if(input.length==0){
            return 0;
        }
        int n = input.length;
        int m = input[0].length;
        int[][] cost = new int[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                cost[i][j]=Integer.MAX_VALUE;
            }
        }
        cost[0][0]=0;
        int[][] pats={
                {1,0,-1,0},
                {0,1,0,-1},
        };
        int[] a = {0,0};
        Deque<int[]> queue = new ArrayDeque<int[]>();
        queue.add(a);

        while(!queue.isEmpty()){
            int size = queue.size();
            while(size-- > 0){
                int k[] = queue.pollFirst();
                int i = k[0];
                int j = k[1];
                int cost1 = cost[i][j];

                for (int l = 0; l < 4; l++) {
                    int x = i+pats[0][l];
                    int y = j+pats[1][l];
                    if(x<0||x>=n||y<0||y>=m||input[x][y]==2){
                        continue;
                    }
                    int costToNext = cost1;
                    if(input[x][y]==0){
                        costToNext+=2;
                    }else{
                        costToNext+=1;
                    }
                    if(costToNext<cost[x][y]){
                        cost[x][y] = costToNext;
                        queue.add(new int[] {x,y});
                    }

                }
            }
        }
        if(cost[n-1][m-1]==Integer.MAX_VALUE){
            return -1;
        }else{
            return cost[n-1][m-1];
        }
    }

    public static void main(String[] args) {
        int[][] in = {{1,1,1,1,0},{0,1,0,1,0},{1,1,2,1,1},{0,2,0,0,1} };
        minSailCost(in);
    }
}
